package by2019;

import java.util.LinkedList;
import java.util.List;

/*
 * LeetCode 102
 * 给定一个二叉树，返回其按层次遍历的节点值
 * 即逐层从左到右访问所有节点。
 */
public class 二叉树广度优先遍历 {
	
	static List<List<Integer>> reList = new LinkedList<List<Integer>>() ;

	public static void main(String[] args) {
		TreeNode root =new TreeNode(3) ;
		root.left = new TreeNode(9) ;
		TreeNode r = new TreeNode(20) ;
		root.right = r ;
		r.left = new TreeNode(15) ;
		r.right = new TreeNode(7) ;
		
		System.out.println(levelOrder(root));

	}
	
	//自己写的广度优先遍历，性能极其垃圾
	//只需要加一个长度判断，在整个二叉树的循环遍历之中加一个for循环遍历每一层
	//每次循环次数为读取到的队列长度
	 public static List<List<Integer>> levelOrder(TreeNode root) {
		 if(root==null)
			 return new LinkedList<List<Integer>>();
		 LinkedList<TreeNode> queue = new LinkedList<TreeNode>() ;
		 List<Integer> list = null ;
		 queue.add(root) ;
		 
		 while(!queue.isEmpty()) {
			 int len = queue.size() ;
			 list = new LinkedList<Integer>() ;
			 for(int i=0;i<len;i++) {
				 TreeNode tree = queue.pollFirst() ;
				 list.add(tree.val);
				 System.out.println("添加到list："+tree.val);
				 if(tree.left!=null) {
					 queue.add(tree.left) ;
					 System.out.println("将树的左子树： "+tree.left.val);
				 }
				 if(tree.right!=null) {
					 queue.add(tree.right) ;
					 System.out.println("添加到右子树： "+tree.right.val);
				 }
			 }
			 reList.add(list) ;
			 System.out.println("添加到reList: "+list.toString());
			 System.out.println("reList: "+reList);
			 //list.clear(); 
			 //System.out.println("clear后的reList："+reList.toString());
		 }
		 return reList ;
	 }

}
